import java.util.*;
class Solution {
    //第N个泰波那契数
    public int tribonacci(int n) {
        int dp[] = new int[n + 1];
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        int a = 0, b = 1, c = 1, d = 0;
        for (int i = 3; i <= n; i++) {
            d = a + b + c;
            a = b;
            b = c;
            c = d;
        }
        return d;
    }

    //三步问题
    public int waysToStep(int n) {
        int dp[] = new int[n + 1];
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 4;
        dp[0] = dp[1] = 1;
        dp[2] = 2;
        int MOD = 1000000007;
        for (int i = 3; i <= n; i++) {
            dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
        }
        return dp[n];
    }

    //使⽤最⼩花费爬楼梯
    public int minCostClimbingStairs(int[] cost) {
        int dp[] = new int[cost.length + 1];
        for (int i = 2; i <= cost.length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.length];
    }

    //解码⽅法
    public int numDecodings(String s) {
        int n = s.length();
        int dp[] = new int[n + 1];
        char[] ch = s.toCharArray();
        dp[0] = 1;
        if (ch[0] != '0')
            dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (ch[i - 1] != '0')
                dp[i] += dp[i - 1];
            if (((ch[i - 2] - '0') * 10 + ch[i - 1] - '0') >= 10 && ((ch[i - 2] - '0') * 10 + ch[i - 1] - '0') <= 26)
                dp[i] += dp[i - 2];
        }
        return dp[s.length()];
    }

    //不同路径
    public int uniquePaths(int m, int n) {
        int dp[][] = new int[m + 1][n + 1];
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }

    //不同路径II
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int dp[][] = new int[m + 1][n + 1];
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (obstacleGrid[i - 1][j - 1] == 0)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }

    //礼物的最⼤价值
    public int jewelleryValue(int[][] frame) {
        int m = frame.length;
        int n = frame[0].length;
        int dp[][] = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }

    //下降路径最⼩和
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int dp[][] = new int[n + 1][n + 2];
        for (int i = 1; i <= n; i++)
            dp[i][0] = dp[i][n + 1] = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j + 1])) + matrix[i - 1][j - 1];
            }
        }
        int ret = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            ret = Math.min(dp[n][i], ret);
        }
        return ret;
    }

    //最⼩路径和
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int dp[][] = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }
        for (int i = 1; i <= n; i++) {
            dp[0][i] = Integer.MAX_VALUE;
        }
        dp[0][1] = dp[1][0] = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }

    //地下城游戏
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int dp[][] = new int[m + 1][n + 1];
        for (int i = m; i >= 0; i--) {
            dp[i][n] = Integer.MAX_VALUE;
        }
        for (int i = n; i >= 0; i--) {
            dp[m][i] = Integer.MAX_VALUE;
        }
        dp[m - 1][n] = dp[m][n - 1] = 1;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = Math.max(1, dp[i][j]);
            }
        }
        return dp[0][0];
    }

    //按摩师
    public int massage(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = nums[0];
        for (int i = 1; i < n; i++) {
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        return Math.max(f[n - 1], g[n - 1]);
    }

    //打家劫舍II
    public int rob(int[] nums) {
        int n = nums.length;
        return Math.max(nums[0] + func(nums, 2, n - 2), func(nums, 1, n - 1));
    }

    public int func(int[] nums, int left, int right) {
        if (left > right) return 0;
        int n = nums.length;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        f[left] = nums[left];
        for (int i = left + 1; i <= right; i++) {
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        return Math.max(f[right], g[right]);
    }

    //删除并获得点数
    public int deleteAndEarn(int[] nums) {
        int[] arr = new int[10001];
        for (int i : nums) {
            arr[i] += i;
        }
        int[] f = new int[10001];
        int[] g = new int[10001];
        for (int i = 1; i < 10001; i++) {
            f[i] = g[i - 1] + arr[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        return Math.max(f[10000], g[10000]);
    }

    //粉刷房⼦
    public int minCost(int[][] costs) {
        int n = costs.length;
        int[][] dp = new int[n + 1][3];
        for (int i = 1; i <= n; i++) {
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
            dp[i][2] = Math.min(dp[i - 1][1], dp[i - 1][0]) + costs[i - 1][2];
        }
        return Math.min(Math.min(dp[n][0], dp[n][1]), dp[n][2]);
    }

    //买卖股票的最佳时机含冷冻期
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][3];
        dp[0][0] = -prices[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][0] + prices[i];
        }
        return Math.max(Math.max(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);
    }

    //买卖股票的最佳时期含⼿续费
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = -prices[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }
        return Math.max(dp[n - 1][0], dp[n - 1][1]);
    }

    //买卖股票的最佳时机III
    public int maxProfitIII(int[] prices) {
        int n = prices.length;
        int INT = 0x3f3f3f3f;
        int[][] f = new int[n][3];
        int[][] g = new int[n][3];
        for (int i = 0; i < 3; i++) {
            f[0][i] = g[0][i] = -INT;
        }
        f[0][0] = -prices[0];
        g[0][0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j > 0)
                    g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        }
        int ret = 0;
        for (int i = 0; i < 3; i++) {
            ret = Math.max(ret, g[n - 1][i]);
        }
        return ret;
    }

    //买卖股票的最佳时机IV
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        k = Math.min(k, n / 2);
        int INT = 0x3f3f3f3f;
        int[][] f = new int[n][k + 1];
        int[][] g = new int[n][k + 1];
        for (int i = 0; i <= k; i++) {
            f[0][i] = g[0][i] = -INT;
        }
        f[0][0] = -prices[0];
        g[0][0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j > 0)
                    g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
            }
        }
        int ret = 0;
        for (int i = 0; i <= k; i++) {
            ret = Math.max(ret, g[n - 1][i]);
        }
        return ret;
    }

    //最大子数组和
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        int ret = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            dp[i] = Math.max(nums[i - 1], dp[i - 1] + nums[i - 1]);
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }

    // 环形⼦数组的最⼤和
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        int sum = 0;
        int fmax = Integer.MIN_VALUE;
        int gmin = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            f[i] = Math.max(x, x + f[i - 1]);
            fmax = Math.max(fmax, f[i]);
            g[i] = Math.min(x, x + g[i - 1]);
            gmin = Math.min(gmin, g[i]);
            sum += x;
        }
        return sum == gmin ? fmax : Math.max(sum - gmin, fmax);
    }

    //乘积最⼤⼦数组
    public int maxProduct(int[] nums) {
        int n = nums.length, fmax = Integer.MIN_VALUE, gmin = Integer.MAX_VALUE, ret = 0;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        f[0] = g[0] = 1;
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1], y = nums[i - 1] * f[i - 1], z = g[i - 1] * nums[i - 1];
            f[i] = Math.max(x, Math.max(y, z));
            g[i] = Math.min(x, Math.min(y, z));
            fmax = Math.max(f[i], fmax);
            gmin = Math.min(g[i], gmin);
        }
        return fmax;
    }

    //乘积为正数的最⻓⼦数组
    public int getMaxLen(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        int ret = 0;
        for (int i = 1; i <= n; i++) {
            if (nums[i - 1] > 0) {
                f[i] = f[i - 1] + 1;
                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
            } else if (nums[i - 1] == 0) {
                continue;
            } else {
                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
                g[i] = f[i - 1] + 1;
            }
            ret = Math.max(ret, f[i]);
        }
        return ret;
    }

    //等差数列划分
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int ret = 0;
        for (int i = 2; i < n; i++) {
            dp[i] = nums[i - 1] - nums[i - 2] == nums[i] - nums[i - 1] ? dp[i - 1] + 1 : 0;
            ret += dp[i];
        }
        return ret;
    }

    //最⻓湍流⼦数组
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = g[0] = 1;
        int ret = 1;
        for (int i = 1; i < n; i++) {
            f[i] = arr[i] < arr[i - 1] ? g[i - 1] + 1 : 1;
            g[i] = arr[i] > arr[i - 1] ? f[i - 1] + 1 : 1;
            ret = Math.max(ret, Math.max(g[i], f[i]));
        }
        return ret;
    }

    //单词拆分
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        s = " " + s;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j >= 1; j--) {
                if (dp[j - 1] && set.contains(s.substring(j, i + 1))) {
                    dp[i] = true;
                    break;
                }
                // if(dp[j-1] && func(s.substring(j,i+1),wordDict)){
                //     dp[i] = true;
                //     break;
                // }
            }
        }
        return dp[n];
    }

    public boolean func(String s, List<String> wordDict) {
        for (int i = 0; i < wordDict.size(); i++) {
            if (s.equals(wordDict.get(i))) {
                return true;
            }
        }
        return false;
    }

    //环绕字符串中唯⼀的⼦字符串
    public int findSubstringInWraproundString(String s) {
        int n = s.length();
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        for (int i = 1; i < n; i++) {
            if (s.charAt(i - 1) + 1 == s.charAt(i) || s.charAt(i - 1) == 'z' && s.charAt(i) == 'a') {
                dp[i] += dp[i - 1];
            }
        }
        int[] hash = new int[26];
        for (int i = 0; i < n; i++) {
            hash[s.charAt(i) - 'a'] = Math.max(dp[i], hash[s.charAt(i) - 'a']);
        }
        int sum = 0;
        for (int i : hash) {
            sum += i;
        }
        return sum;
    }

    //最⻓递增⼦序列
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int ret = 1;
        int count = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }

    //摆动序列
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        int ret = 1;
        for (int i = 0; i < n; i++) {
            f[i] = g[i] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    g[i] = Math.max(f[j] + 1, g[i]);
                } else if (nums[i] < nums[j]) {
                    f[i] = Math.max(g[j] + 1, f[i]);
                }
            }
            ret = Math.max(ret, Math.max(g[i], f[i]));
        }
        return ret;
    }

    //最⻓递增⼦序列的个数
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] count = new int[n];
        int[] len = new int[n];
        int retlen = 1;
        int retcount = 1;
        for (int i = 0; i < n; i++) {
            len[i] = count[i] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    if (len[i] < len[j] + 1) {
                        count[i] = count[j];
                        len[i] = len[j] + 1;
                    } else if (len[j] + 1 == len[i]) {
                        count[i] += count[j];
                    }
                }
            }
            if (retlen == len[i]) {
                retcount += count[i];
            } else if (retlen < len[i]) {
                retlen = len[i];
                retcount = count[i];
            }
        }
        return retcount;
    }

    //最⻓数对链
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        int n = pairs.length;
        int[] dp = new int[n];
        int ret = 1;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (pairs[i][0] > pairs[j][1]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                    ret = Math.max(ret, dp[i]);
                }
            }
        }
        return ret;
    }

    //最⻓定差⼦序列
    public int longestSubsequence(int[] arr, int difference) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int ret = 0;
        for (int i : arr) {
            map.put(i, map.getOrDefault(i - difference, 0) + 1);
            ret = Math.max(ret, map.get(i));
        }
        return ret;
    }

    //最⻓的斐波那契⼦序列的⻓度
    public int lenLongestFibSubseq(int[] arr) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int n = arr.length;
        int[][] dp = new int[n][n];
        int ret = 2;
        for (int i = 0; i < n; i++) {
            map.put(arr[i], i);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = 2;
            }
        }
        for (int i = 2; i < n; i++) {
            for (int j = 1; j < i; j++) {
                int a = arr[i] - arr[j];
                if (a < arr[j] && map.containsKey(a)) {
                    dp[j][i] = dp[map.get(a)][j] + 1;
                }
                ret = Math.max(dp[j][i], ret);
            }
        }
        return ret < 3 ? 0 : ret;
    }

    public int lenLongestFibSubseq1(int[] arr) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int n = arr.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], 2);
        }
        map.put(arr[0], 0);
        int ret = 2;
        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int a = arr[j] - arr[i];
                if (map.containsKey(a)) {
                    dp[i][j] = dp[map.get(a)][i] + 1;
                    ret = Math.max(ret, dp[i][j]);
                }
            }
            map.put(arr[i], i);
        }
        return ret < 3 ? 0 : ret;
    }

    //最⻓等差数列
    public int longestArithSeqLength(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(nums[0], 0);
        int n = nums.length;
        int ret = 2;
        int[][] dp = new int[n][n];
        // for(int i = 0;i < n;i++){
        //     map.put(nums[i],i);
        // }用这个需要判断位置
        // for(int i = 0;i < n;i++){
        //     for(int j = 0;j < n;j++){
        //         dp[i][j] = 2;
        //     }
        // }
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], 2);
        }
        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int a = 2 * nums[i] - nums[j];
                if (map.containsKey(a)) {
                    dp[i][j] = dp[map.get(a)][i] + 1;
                    ret = Math.max(ret, dp[i][j]);
                }
            }
            map.put(nums[i], i);
        }
        return ret;
    }

    //等差数列划分II-⼦序列
    public int numberOfArithmeticSlices1(int[] nums) {
        HashMap<Long, ArrayList<Integer>> map = new HashMap<>();
        int n = nums.length;
        int sum = 0;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            long tmp = (long) nums[i];
            if (!map.containsKey(tmp)) {
                map.put(tmp, new ArrayList<Integer>());
            }
            map.get(tmp).add(i);
        }
        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long a = 2L * nums[i] - nums[j];
                if (map.containsKey(a)) {
                    for (int k : map.get(a)) {
                        if (k < i) {
                            dp[i][j] += dp[k][i] + 1;
                        } else {
                            break;
                        }
                    }
                }
                sum += dp[i][j];
            }
        }
        return sum;
    }

    //回⽂⼦串
    public int countSubstrings(String s) {
        int n = s.length();
        char[] ch = s.toCharArray();
        boolean[][] dp = new boolean[n][n];
        int sum = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (ch[i] == ch[j]) {
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                }
                if (dp[i][j]) {
                    sum++;
                }
            }
        }
        return sum;
    }

    //最⻓回⽂⼦串
    public String longestPalindrome(String s) {
        int n = s.length();
        char[] ch = s.toCharArray();
        boolean[][] dp = new boolean[n][n];
        int len = 1, begin = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (ch[i] == ch[j]) {
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                }
                if (dp[i][j] && j - i + 1 > len) {
                    len = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + len);
    }

    //回⽂串分割IV
    public boolean checkPartitioning(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = i; j + 1 < n; j++) {
                if (dp[0][i] && dp[i + 1][j] && dp[j + 1][n - 1]) {
                    return true;
                }
            }
        }
        return false;
    }

    //分割回⽂串II
    public int minCut(String s) {
        int n = s.length();
        boolean[][] ss = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    ss[i][j] = i + 1 < j ? ss[i + 1][j - 1] : true;
                }
            }
        }
        int[] dp = new int[n];
        int ret = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < n; i++) {
            if (ss[0][i]) {
                dp[i] = 0;
            } else {
                for (int j = i; j >= 0; j--) {
                    if (ss[j][i]) {
                        dp[i] = Math.min(dp[j - 1] + 1, dp[i]);
                    }
                }
            }
        }
        return dp[n - 1];
    }

    //最⻓回⽂⼦序列
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }

    //让字符串成为回⽂串的最⼩插⼊次数
    public int minInsertions(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i + 1][j] + 1, dp[i][j - 1] + 1);
                }
            }
        }
        return dp[0][n - 1];
    }

    //最⻓公共⼦序列
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();
        int[][] dp = new int[n + 1][m + 1];
        text1 = ' ' + text1;
        text2 = ' ' + text2;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (text1.charAt(i) == text2.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n][m];
    }

    //不相交的线
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n][m];
    }

    //不同的⼦序列
    public int numDistinct(String s, String t) {
        int n = s.length();
        int m = t.length();
        int[][] dp = new int[m + 1][n + 1];
        s = ' ' + s;
        t = ' ' + t;
        for (int i = 0; i <= n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i][j - 1];
                if (t.charAt(i) == s.charAt(j)) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }

    //通配符匹配
    public boolean isMatch1(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            if (p.charAt(i - 1) == '*') {
                dp[0][i] = true;
            } else {
                break;
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }

    //正则表达式
    public boolean isMatch2(String s, String p) {
        int n = s.length();
        int m = p.length();
        s = ' ' + s;
        p = ' ' + p;
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        for (int i = 2; i <= m; i += 2) {
            if (p.charAt(i) == '*') {
                dp[0][i] = true;
            } else {
                break;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p.charAt(j) == '*') {
                    dp[i][j] = dp[i][j - 2] || (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i)) && dp[i - 1][j];

                } else {
                    dp[i][j] = (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i)) && dp[i - 1][j - 1];
                }
            }
        }
        return dp[n][m];
    }

    //交错字符串
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length();
        int m = s2.length();
        if (n + m != s3.length()) {
            return false;
        }
        s1 = " " + s1;
        s2 = " " + s2;
        s3 = " " + s3;
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        for (int i = 1; i <= m; i++) {
            if (s2.charAt(i) == s3.charAt(i)) {
                dp[0][i] = true;
            } else {
                break;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (s1.charAt(i) == s3.charAt(i)) {
                dp[i][0] = true;
            } else {
                break;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = ((s1.charAt(i) == s3.charAt(i + j)) && dp[i - 1][j]) ||
                        ((s2.charAt(j) == s3.charAt(i + j)) && dp[i][j - 1]);
            }
        }
        return dp[n][m];
    }
    //两个字符串的最⼩ASCII删除和
//    public int minimumDeleteSum(String s1, String s2) {
//        int m = s1.length();
//        int n = s2.length();
//        int[][] dp = new int[m + 1][n + 1];
//        int sum = 0;
//        for (char ch : s1.toCharArray()) {
//            sum += ch;
//        }
//        for (char ch : s2.toCharArray()) {
//            sum += ch;
//        }
//        for (int i = 1; i <= m; i++) {
//            for (int j = 1; j <= n; j++) {
//                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
//                if (s1.charAt(i-1) == s2.charAt(j-1)) {
//                    dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - 1] + s1.charAt(i-1));
//                }
//            }
//        }
//        return sum - 2 * dp[m][n];
//    }
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        s1 = " " + s1;
        s2 = " " + s2;
        int[][] dp = new int[m + 1][n + 1];
        int sum = 0;
        // for (char ch : s1.toCharArray()) {
        //     sum += ch;
        // }
        // for (char ch : s2.toCharArray()) {
        //     sum += ch;
        // }
        for(int i = 1;i <= n;i++){
            sum+=s2.charAt(i);
        }
        for(int i = 1;i <= m;i++){
            sum+=s1.charAt(i);
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                if (s1.charAt(i) == s2.charAt(j)) {
                    dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - 1] + s1.charAt(i));
                }
            }
        }
        return sum - 2 * dp[m][n];
    }
    //最⻓重复⼦数组
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[][] dp = new int[m+1][n+1];
        int ret = 0;
        for(int i = 1;i <= m;i++){
            for(int j = 1;j <= n;j++){
                if(nums1[i-1] == nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    ret = Math.max(dp[i][j],ret);
                }
            }
        }
        return ret;
    }
    //01背包
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int V = in.nextInt();
        int[] v = new int[n + 1];
        int[] w = new int[n + 1];
        int[] dp1 = new int[1001];
        for (int i = 1; i <= n; i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        for (int i = 1; i <= n; i++)
            for (int j = V; j >= v[i]; j--) // 修改遍历顺序
                dp1[j] = Math.max(dp1[j], dp1[j - v[i]] + w[i]);
        System.out.println(dp1[V]);
        int[] dp2 = new int[1001];
        for (int i = 1; i <= V; i++)dp2[i] = -1;
        for (int i = 1; i <= n; i++)
            for (int j = V; j >= v[i]; j--)
                if (dp2[j - v[i]] != -1)
                    dp2[j] = Math.max(dp2[j], dp2[j - v[i]] + w[i]);
        System.out.println(dp2[V] == -1 ? 0 : dp2[V]);
    }
    //分割等和⼦集
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int i : nums)sum += i;
        if(sum % 2 != 0)return false;
        sum /= 2;
        int n = nums.length;
        boolean[] dp = new boolean[sum+1];
        dp[0] = true;
        for(int i = 1;i <= n;i++)
            for(int j = sum;0 <= j;j--){
                dp[j] = dp[j];
                if(j >= nums[i-1])dp[j] = dp[j] || dp[j-nums[i-1]];
            }
        return dp[sum];
    }
    //⽬标和
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0,n = nums.length;
        for(int i : nums)sum += i;
        int a = (sum + target)/2;
        if((sum + target) % 2 != 0 || a < 0)return 0;
        int[] dp = new int[a+1];
        dp[0] = 1;
        for(int i = 1;i <= n;i++)
            for(int j = a;0 <= j;j--){
                dp[j] = dp[j];
                if(j >= nums[i-1])dp[j] += dp[j-nums[i-1]];
            }
        return dp[a];
    }
    //最后⼀块⽯头的重量II
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for(int i : stones)sum += i;
        int a = sum / 2;
        int[] dp = new int[a+1];
        for(int i = 1;i <= n;i++)
            for(int j = a; j >= stones[i-1];j--){
                dp[j] = Math.max(dp[j],dp[j-stones[i-1]] + stones[i-1]);
            }
        return 2*dp[a] - sum > 0 ? 2*dp[a] - sum : sum - 2*dp[a];
    }
    //完全背包
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        int[] dp = new int[b + 1];
        int[] v = new int[a + 1];
        int[] w = new int[a + 1];
        for (int i = 1; i <= a; i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        for (int i = 1; i <= a; i++)
            for (int j = 0; j <= b; j++) {
                dp[j] = dp[j];
                if (j >= v[i])dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
            }
        System.out.println(dp[b]);
        int INT = 0x3f3f3f3f;
        int[] dp1 = new int[b + 1];
        for (int i = 1; i <= b; i++)dp1[i] = -INT;
        for (int i = 1; i <= a; i++)
            for (int j = v[i]; j <=b ; j++) {
                dp1[j] = Math.max(dp1[j], dp1[j - v[i]] + w[i]);
            }
        System.out.println(dp1[b] < 0  ? 0 : dp1[b]);
    }
    //零钱兑换
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[] dp = new int[amount+1];
        if(amount == 0)return 0;
        int INT = 0x3f3f3f3f;
        for(int i = 1;i <= amount;i++)dp[i] = INT;
        for(int i = 1;i <= n;i++)
            for(int j = coins[i-1]; j <= amount;j++){
                dp[j] = Math.min(dp[j],dp[j-coins[i-1]] + 1);
            }
        return dp[amount] >= INT ? -1 :dp[amount];
    }
    //零钱兑换II
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for(int i : coins)
            for(int j = i;j <= amount;j++)
                dp[j] += dp[j-i];
        return dp[amount];
    }
    //完全平⽅数
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        for(int i = 1; i<= n;i++)dp[i] = 0x3f3f3f3f;
        for(int i = 1; i <= Math.sqrt(n);i++)
            for(int j = i*i;j <= n;j++)
                dp[j] = Math.min(dp[j],dp[j-i*i] + 1);
        return dp[n];
    }
    //⼀和零
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        //int a = 0, b = 0;
        for (int i = 1; i <= strs.length; i++) {
            int a = 0, b = 0;
            for (char ch : strs[i - 1].toCharArray())
                if (ch == '0')
                    a++;
                else
                    b++;
            for (int j = m; a <= j; j--)
                for (int k = n; b <= k; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - a][k - b] + 1);
                }
        }
        return dp[m][n];
    }
    //盈利计划
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int[][] dp = new int[n+1][minProfit+1];
        for(int i = 0;i <= n;i++)dp[i][0] = 1;
        for(int i = 0;i < group.length;i++)
            for(int j = n;group[i] <= j;j--)
                for(int k = minProfit;0 <= k;k--){
                    dp[j][k] += dp[j-group[i]][Math.max(0,k-profit[i])];
                    dp[j][k] %= (1e9 + 7);
                }
        return dp[n][minProfit];
    }
    //组合总数IV
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for(int j = 1;j <= target;j++)
            for(int i : nums)
                if(j >= i)dp[j] += dp[j-i];
        return dp[target];
    }
    //不同的⼆叉搜索树
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= i;j++)
                dp[i] += dp[i-j]*dp[j-1];
        return dp[n];
    }
}